package offerbook;

/**
 * @date 2019/11/8 0008 上午 10:12
 *
 * 不用 加减乘除 做  加法运算。
 *
 * 对于10进制加法：先把所有把对应位相加【不考虑进位】，
 * 然后处理进位，把进位加到上一位，直到进位为0
 *
 * 对于2进制：把所有的对应为相加，只有1和1，0和0的时候是0，其他两种是1.是异或的结果。
 *
 * 然后记录对应的进位，只有1和1的时候才有进位，也就是与的结果。
 *
 * 把这个进行左移一位，与上次求得的sum相加（还是异或，重复上面过程，直到进位为0）
 *
 * 注意：
 * 有负数也没关系，因为会以补码形式进行二进制运算。溢出也没关系，二进制也会溢出。
 */
public class Code47_SumWithNoAdd {


    public int Add(int num1,int num2) {

        //这样赋值，是防止num2 = 0，这样直接返回num1
        int sum = num1;
        int carry = 0;
        while (num2 != 0){
            //把num1与num2以二进制形式相加，不考虑任何进位
            sum = (num1 ^ num2);
            //标记num1与num2产生的进位位置
            carry = (num1 & num2);
            //记录sum
            num1 = sum;
            //把进位左移一位，然后和sum再次相加，重复上面过程
            num2 = (carry << 1);
        }
        return sum;
    }

    /**
     * 拓展：不用额外空间交换a和b两个值
     */

    public void swap1(int a,int b){
        a = a ^ b;
        b = a ^ b; // b = (a^b)^b = a ^(b^b) = a^ 0 = a
        a = a ^ b; // a = (a^b)^a = b
    }
    public void swap2(int a,int b){
       a = a + b;
       b = a - b; // b = a + b - b = a
       a = a - b; // a = a -b = a+b - a = b
    }
}
